package com.easy.carl.algorithm.tree;

import com.easy.leetcode.tree.TreeNode;

import java.util.Arrays;

/**
 * @ClassName ReConstructBinaryTree
 * @Description TODO
 * @Author zheng
 * @Date 2022/3/11 9:51
 * @Version 1.0
 **/
public class ReConstructBinaryTree {

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        TreeNode node = null;
        if (pre != null && pre.length > 0) {
            node = new TreeNode(pre[0]);
        } else {
            return null;
        }
        //获取左右子树的分割点
        int index = getIndex(vin, pre[0]);
        //递归的进行左侧节点判断
        node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, 1 + index), Arrays.copyOfRange(vin, 0, index));
        //递归的进行右侧节点判断
        node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, 1 + index, pre.length), Arrays.copyOfRange(vin, index + 1, vin.length));
        return node;
    }

    private int getIndex(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
